package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

/**
 * 0108.将有序数组转换为二叉搜索树
 *
 * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 *
 * @author Liyc
 * @date 2024/1/16 14:50
 **/

public class Solution26 {
    /**
     * 递归法-左闭右闭
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST1(nums, 0, nums.length - 1);
    }
    public TreeNode sortedArrayToBST1(int[] nums, int left, int right) {
        if (left > right) return null;

        int mid = left + (right + left) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST1(nums, left, mid - 1);
        node.right = sortedArrayToBST1(nums, mid + 1, right);
        return node;
    }
}
